#include <stdio.h>
#include <string.h>

void get_next(char *T, char* next)
{
	int j = 0;
	int i = 1;
	next[1] = 0;
	
	while (i < T[0])
	{
		if (0 == j || T[i] == T[j])
		{
			i++;
			j++;
			next[i] = j;
		}
		else
		{
			j = next[j];
		}
	}
}

int index_KMP(char *S, char *T, int pos)
{
    int i = pos;
	int j = 1;
	char next[255];
	get_next(T, next);
	
	while (i <= S[0] && j <= T[0])
	{
		if (j == 0 || S[i] == T[j])
		{
			i++;
			j++;
		}
		else
		{
			j = next[j];
		}
	}
	
	if (j > T[0])
	{
		return i - T[0];
	}
	else
	{
		return -1;
	}
}

int main(void)
{
	char * s = "I love programming very much";
	char * t = "very";
	
	char s1[strlen(s) + 1];
	s1[0] = strlen(s);
	strcpy(s1 + 1, s);
	
	char t1[strlen(t) + 1];
	t1[0] = strlen(t);
	strcpy(t1 + 1, t);
	
	int index = index_KMP(s1, t1, 0);
	printf("index of %s is %d\n", t, index);
	return 0;
}
